package i_SegmentTree;

/**
    
     * @author ghqs
     * 是否递归？一个递归单元是什么样的？ *递归的状态变量是谁？* 需不需要给上层传值(可以先假设不需要)？            ————确认参数和语意；
     * 递归宏观是什么样子展开的？ *多路吗？* 每一路都应该符合的终止条件是啥？回到倒数第二层要传值吗？				————终止条件；                                                           
	 * （每一层的递归 要执行什么操作吗？）																（————处理逻辑；一般，查询或修改单个确认目标都不需要）   
	 * 每一层想开始递归时要分哪几种情况吗？ 每一种情况里，还要分路递归吗？如果分路(根据语意分路)，要对各路结果进行merge吗？      			————开始递归；    				
	 * 						 ps：分路递归时，非首次递归在首次递归的每一层里都是挂件，都是跟随当前递归参数来执行；首次递归完全返回后，紧随其后的递归就成为了首次递归；
	 
*/


//几种典型的模板
public class TypeOfRecursion<E> {           //写递归算法的第一步应该是*确定语意*，这样才能递归起来；其实写任何方法的第一步都是确认语意，不然写什么？只是语意对于递归来说尤为重要；

    private E[] tree;
    private E[] data;
    private Merger<E> merger;

    public TypeOfRecursion(E[] arr, Merger<E> merger){
        this.merger = merger;
        
        data = (E[])new Object[arr.length];
        for(int i = 0 ; i < arr.length ; i ++)
            data[i] = arr[i];

        tree = (E[])new Object[4 * arr.length];
        buildSegmentTree(0, 0, arr.length - 1);
    }

//    //Type1:向下构造式递归，边递归边处理；
//    private void abc(argR){
//
//        if(what){
//            doWhat;				//结束条件并不是一蹴而就的，如果有多种情况，就把多种情况的结束条件能合并的合并 然后都写出来就好了
//            return;   	//递归终止条件；递归的最大范围，和构造逻辑解耦。如果在处理逻辑中满足了目标然后return了，这算的是处理逻辑的一部分，在此不用考虑；
//        }
//
//        current argR:doWhat...     //处理逻辑，构造逻辑；正常递归过程中，若满足了目标，可以结束递归 直接return；
//
//        abc(toDown/toNext/toBreakDown); //递归驱动，动起来；
//    }

    
    
    
    //Type2:向上构造式递归；递归占位，到底后折返执行处理逻辑；
    //这里是全部递归分支都占位，全部到底后回跳到上一层，然后对底层结果进行处理；
    //我猜将来还会遇到类似的改编，可以在不同递归分支返回后各自做处理，最后再总处理；
    //总之，理解方式就是：递归到底执行底部构造逻辑，结束递归折返到父层，接着向下执行...父层全部执行完后return，就会折返到父层的父层；此外：在每次折返的时候，都可以带着数据折返到父层，即设置递归的返回值；
    private void buildSegmentTree(int treeIndex, int l, int r){// 在treeIndex的位置创建表示区间[l...r]的线段树

        if(l == r){ 					//递归的结束条件，与处理逻辑解耦。  递归到底时的处理逻辑；
            tree[treeIndex] = data[l];    //结束条件并不是一蹴而就的，如果有多种情况，就把多种情况的结束条件能合并的合并 然后都写出来就好了
            return;
        }

//———————————————————————//递归的驱动—————————————————————————————————————————————————————       
        int leftTreeIndex = leftChild(treeIndex);int rightTreeIndex = rightChild(treeIndex);int mid = l + (r - l) / 2;
        buildSegmentTree(leftTreeIndex, l, mid);
        buildSegmentTree(rightTreeIndex, mid + 1, r);
//————————————————————————————————————————————————————————————————————————————
        
        //处理逻辑，构造逻辑；
        tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
        //return;
    }
	private int rightChild(int treeIndex) {
		// TODO 自动生成的方法存根
		return 0;
	}
	private int leftChild(int treeIndex) {
		// TODO 自动生成的方法存根
		return 0;
	}

	
	//Type3:无处理逻辑的递归/仅返回最底层处理结果的递归；常用于递归查询(+处理)；
	//可以理解为type1 or type2的特殊情况，只是不做处理；
    private E query(int treeIndex, int l, int r, int queryL, int queryR){// 在以treeIndex为根的线段树中[l...r]的范围里，搜索区间[queryL...queryR]的值

        if(l == queryL && r == queryR)   		//递归结束条件，最后一层处理逻辑
            return tree[treeIndex];			//结束条件并不是一蹴而就的，如果有多种情况，就把多种情况的结束条件能合并的合并 然后都写出来就好了
        
//———————————————————————//递归驱动；无处理逻辑，仅将最底层处理逻辑的结果 折返返回———————————————————————————————————————————
        int mid = l + (r - l) / 2;                   
        // treeIndex的节点分为[l...mid]和[mid+1...r]两部分
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        if(queryL >= mid + 1)
            return query(rightTreeIndex, mid + 1, r, queryL, queryR);
        else if(queryR <= mid)
            return query(leftTreeIndex, l, mid, queryL, queryR);
        else {
        	 E leftResult = query(leftTreeIndex, l, mid, queryL, mid);
             E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);
             return merger.merge(leftResult, rightResult);
        }
//——————————————————————————————————————————————————————————————————选自线段树       
    }
}
